QUnit.module('Trie', () =>
{
    QUnit.test('should create trie', (assert) =>
    {
        const trie = new ds.Trie();

        assert.deepEqual(trie != null, true);
        assert.deepEqual(trie.head.toString(), '*');
    });

    QUnit.test('should add words to trie', (assert) =>
    {
        const trie = new ds.Trie();

        trie.addWord('cat');

        assert.deepEqual(trie.head.toString(), '*:c');
        assert.deepEqual(trie.head.getChild('c').toString(), 'c:a');

        trie.addWord('car');
        assert.deepEqual(trie.head.toString(), '*:c');
        assert.deepEqual(trie.head.getChild('c').toString(), 'c:a');
        assert.deepEqual(trie.head.getChild('c').getChild('a').toString(), 'a:t,r');
        assert.deepEqual(trie.head.getChild('c').getChild('a').getChild('t').toString(), 't*');
    });

    QUnit.test('should delete words from trie', (assert) =>
    {
        const trie = new ds.Trie();

        trie.addWord('carpet');
        trie.addWord('car');
        trie.addWord('cat');
        trie.addWord('cart');
        assert.deepEqual(trie.doesWordExist('carpet'), true);
        assert.deepEqual(trie.doesWordExist('car'), true);
        assert.deepEqual(trie.doesWordExist('cart'), true);
        assert.deepEqual(trie.doesWordExist('cat'), true);

        // Try to delete not-existing word first.
        trie.deleteWord('carpool');
        assert.deepEqual(trie.doesWordExist('carpet'), true);
        assert.deepEqual(trie.doesWordExist('car'), true);
        assert.deepEqual(trie.doesWordExist('cart'), true);
        assert.deepEqual(trie.doesWordExist('cat'), true);

        trie.deleteWord('carpet');
        assert.deepEqual(trie.doesWordExist('carpet'), false);
        assert.deepEqual(trie.doesWordExist('car'), true);
        assert.deepEqual(trie.doesWordExist('cart'), true);
        assert.deepEqual(trie.doesWordExist('cat'), true);

        trie.deleteWord('cat');
        assert.deepEqual(trie.doesWordExist('car'), true);
        assert.deepEqual(trie.doesWordExist('cart'), true);
        assert.deepEqual(trie.doesWordExist('cat'), false);

        trie.deleteWord('car');
        assert.deepEqual(trie.doesWordExist('car'), false);
        assert.deepEqual(trie.doesWordExist('cart'), true);

        trie.deleteWord('cart');
        assert.deepEqual(trie.doesWordExist('car'), false);
        assert.deepEqual(trie.doesWordExist('cart'), false);
    });

    QUnit.test('should suggests next characters', (assert) =>
    {
        const trie = new ds.Trie();

        trie.addWord('cat');
        trie.addWord('cats');
        trie.addWord('car');
        trie.addWord('caption');

        assert.deepEqual(trie.suggestNextCharacters('ca'), ['t', 'r', 'p']);
        assert.deepEqual(trie.suggestNextCharacters('cat'), ['s']);
        assert.deepEqual(trie.suggestNextCharacters('cab'), null);
    });

    QUnit.test('should check if word exists', (assert) =>
    {
        const trie = new ds.Trie();

        trie.addWord('cat');
        trie.addWord('cats');
        trie.addWord('carpet');
        trie.addWord('car');
        trie.addWord('caption');

        assert.deepEqual(trie.doesWordExist('cat'), true);
        assert.deepEqual(trie.doesWordExist('cats'), true);
        assert.deepEqual(trie.doesWordExist('carpet'), true);
        assert.deepEqual(trie.doesWordExist('car'), true);
        assert.deepEqual(trie.doesWordExist('cap'), false);
        assert.deepEqual(trie.doesWordExist('call'), false);
    });
});


QUnit.module('TrieNode', () =>
{
    QUnit.test('should create trie node', (assert) =>
    {
        const trieNode = new ds.TrieNode('c', true);

        assert.deepEqual(trieNode.character, 'c');
        assert.deepEqual(trieNode.isCompleteWord, true);
        assert.deepEqual(trieNode.toString(), 'c*');
    });

    QUnit.test('should add child nodes', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');

        trieNode.addChild('a', true);
        trieNode.addChild('o');

        assert.deepEqual(trieNode.toString(), 'c:a,o');
    });

    QUnit.test('should get child nodes', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');

        trieNode.addChild('a');
        trieNode.addChild('o');

        assert.deepEqual(trieNode.getChild('a').toString(), 'a');
        assert.deepEqual(trieNode.getChild('a').character, 'a');
        assert.deepEqual(trieNode.getChild('o').toString(), 'o');
        assert.deepEqual(trieNode.getChild('b'), undefined);
    });

    QUnit.test('should check if node has children', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');

        assert.deepEqual(trieNode.hasChildren(), false);

        trieNode.addChild('a');

        assert.deepEqual(trieNode.hasChildren(), true);
    });

    QUnit.test('should check if node has specific child', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');

        trieNode.addChild('a');
        trieNode.addChild('o');

        assert.deepEqual(trieNode.hasChild('a'), true);
        assert.deepEqual(trieNode.hasChild('o'), true);
        assert.deepEqual(trieNode.hasChild('b'), false);
    });

    QUnit.test('should suggest next children', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');

        trieNode.addChild('a');
        trieNode.addChild('o');

        assert.deepEqual(trieNode.suggestChildren(), ['a', 'o']);
    });

    QUnit.test('should delete child node if the child node has NO children', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');
        trieNode.addChild('a');
        assert.deepEqual(trieNode.hasChild('a'), true);

        trieNode.removeChild('a');
        assert.deepEqual(trieNode.hasChild('a'), false);
    });

    QUnit.test('should NOT delete child node if the child node has children', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');
        trieNode.addChild('a');
        const childNode = trieNode.getChild('a');
        childNode.addChild('r');

        trieNode.removeChild('a');
        assert.deepEqual(trieNode.hasChild('a'), true);
    });

    QUnit.test('should NOT delete child node if the child node completes a word', (assert) =>
    {
        const trieNode = new ds.TrieNode('c');
        const IS_COMPLETE_WORD = true;
        trieNode.addChild('a', IS_COMPLETE_WORD);

        trieNode.removeChild('a');
        assert.deepEqual(trieNode.hasChild('a'), true);
    });
});
